/*
 * Copyright (C) 2009 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef PINYINIME_ANDPY_INCLUDE_MATRIXSEARCH_H__
#define PINYINIME_ANDPY_INCLUDE_MATRIXSEARCH_H__

#include <stdlib.h>
#include "./atomdictbase.h"
#include "./dicttrie.h"
#include "./searchutility.h"
#include "./spellingtrie.h"
#include "./splparser.h"

namespace ime_pinyin
{

	static const size_t kMaxRowNum = kMaxSearchSteps;

	typedef struct {
		// MileStoneHandle objects for the system and user dictionaries.
		MileStoneHandle dict_handles[2];
		// From which DMI node. -1 means it's from root.
		PoolPosType dmi_fr;
		// The spelling id for the Pinyin string from the previous DMI to this node.
		// If it is a half id like Shengmu, the node pointed by dict_node is the first
		// node with this Shengmu,
		uint16 spl_id;
		// What's the level of the dict node. Level of root is 0, but root is never
		// recorded by dict_node.
		unsigned char dict_level: 7;
		// If this node is for composing phrase, this bit is 1.
		unsigned char c_phrase: 1;
		// Whether the spl_id is parsed with a split character at the end.
		unsigned char splid_end_split: 1;
		// What's the length of the spelling string for this match, for the whole
		// word.
		unsigned char splstr_len: 7;
		// Used to indicate whether all spelling ids from the root are full spelling
		// ids. This information is useful for keymapping mode(not finished). Because
		// in this mode, there is no clear boundaries, we prefer those results which
		// have full spelling ids.
		unsigned char all_full_id: 1;
	} DictMatchInfo, *PDictMatchInfo;

	typedef struct MatrixNode {
		LemmaIdType id;
		float score;
		MatrixNode *from;
		// From which DMI node. Used to trace the spelling segmentation.
		PoolPosType dmi_fr;
		uint16 step;
	} MatrixNode, *PMatrixNode;

	typedef struct {
		// The MatrixNode position in the matrix pool
		PoolPosType mtrx_nd_pos;
		// The DictMatchInfo position in the DictMatchInfo pool.
		PoolPosType dmi_pos;
		uint16 mtrx_nd_num;
		uint16 dmi_num: 15;
		// Used to indicate whether there are dmi nodes in this step with full
		// spelling id. This information is used to decide whether a substring of a
		// valid Pinyin should be extended.
		//
		// Example1: shoudao
		// When the last char 'o' is added, the parser will find "dao" is a valid
		// Pinyin, and because all dmi nodes at location 'd' (including those for
		// "shoud", and those for "d") have Shengmu id only, so it is not necessary
		// to extend "ao", otherwise the result may be "shoud ao", that is not
		// reasonable.
		//
		// Example2: hengao
		// When the last 'o' is added, the parser finds "gao" is a valid Pinyin.
		// Because some dmi nodes at 'g' has Shengmu ids (hen'g and g), but some dmi
		// nodes at 'g' has full ids ('heng'), so it is necessary to extend "ao", thus
		// "heng ao" can also be the result.
		//
		// Similarly, "ganga" is expanded to "gang a".
		//
		// For Pinyin string "xian", because "xian" is a valid Pinyin, because all dmi
		// nodes at 'x' only have Shengmu ids, the parser will not try "x ian" (and it
		// is not valid either). If the parser uses break in the loop, the result
		// always be "xian"; but if the parser uses continue in the loop, "xi an" will
		// also be tried. This behaviour can be set via the function
		// set_xi_an_switch().
		uint16 dmi_has_full_id: 1;
		// Points to a MatrixNode of the current step to indicate which choice the
		// user selects.
		MatrixNode *mtrx_nd_fixed;
	} MatrixRow, *PMatrixRow;

	// When user inputs and selects candidates, the fixed lemma ids are stored in
	// lma_id_ of class MatrixSearch, and fixed_lmas_ is used to indicate how many
	// lemmas from the beginning are fixed. If user deletes Pinyin characters one
	// by one from the end, these fixed lemmas can be unlocked one by one when
	// necessary. Whenever user deletes a Chinese character and its spelling string
	// in these fixed lemmas, all fixed lemmas will be merged together into a unit
	// named ComposingPhrase with a lemma id kLemmaIdComposing, and this composing
	// phrase will be the first lemma in the sentence. Because it contains some
	// modified lemmas (by deleting a character), these merged lemmas are called
	// sub lemmas (sublma), and each of them are represented individually, so that
	// when user deletes Pinyin characters from the end, these sub lemmas can also
	// be unlocked one by one.
	typedef struct {
		uint16 spl_ids[kMaxRowNum];
		uint16 spl_start[kMaxRowNum];
		char16 chn_str[kMaxRowNum];       // Chinese string.
		uint16 sublma_start[kMaxRowNum];  // Counted in Chinese characters.
		size_t sublma_num;
		uint16 length;                    // Counted in Chinese characters.
	} ComposingPhrase, *TComposingPhrase;

	class MatrixSearch
	{
	private:
		// If it is true, prediction list by string whose length is greater than 1
		// will be limited to a reasonable number.
		static const bool kPredictLimitGt1 = false;

		// If it is true, the engine will prefer long history based prediction,
		// for example, when user inputs "BeiJing", we prefer "DaXue", etc., which are
		// based on the two-character history.
		static const bool kPreferLongHistoryPredict = true;

		// If it is true, prediction will only be based on user dictionary. this flag
		// is for debug purpose.
		static const bool kOnlyUserDictPredict = false;

		// The maximum buffer to store LmaPsbItems.
		static const size_t kMaxLmaPsbItems = 1450;

		// How many rows for each step.
		static const size_t kMaxNodeARow = 5;

		// The maximum length of the sentence candidates counted in chinese
		// characters
		static const size_t kMaxSentenceLength = 16;

		// The size of the matrix node pool.
		static const size_t kMtrxNdPoolSize = 200;

		// The size of the DMI node pool.
		static const size_t kDmiPoolSize = 800;

		// Used to indicate whether this object has been initialized.
		bool inited_;

		// Spelling trie.
		const SpellingTrie *spl_trie_;

		// Used to indicate this switcher status: when "xian" is parseed, should
		// "xi an" also be extended. Default is false.
		// These cases include: xia, xian, xiang, zhuan, jiang..., etc. The string
		// should be valid for a FULL spelling, or a combination of two spellings,
		// first of which is a FULL id too. So even it is true, "da" will never be
		// split into "d a", because "d" is not a full spelling id.
		bool xi_an_enabled_;

		// System dictionary.
		DictTrie *dict_trie_;

		// User dictionary.
		AtomDictBase *user_dict_;

		// Spelling parser.
		SpellingParser *spl_parser_;

		// The maximum allowed length of spelling string (such as a Pinyin string).
		size_t max_sps_len_;

		// The maximum allowed length of a result Chinese string.
		size_t max_hzs_len_;

		// Pinyin string. Max length: kMaxRowNum - 1
		char pys_[kMaxRowNum];

		// The length of the string that has been decoded successfully.
		size_t pys_decoded_len_;

		// Shared buffer for multiple purposes.
		size_t *share_buf_;

		MatrixNode *mtrx_nd_pool_;
		PoolPosType mtrx_nd_pool_used_;    // How many nodes used in the pool
		DictMatchInfo *dmi_pool_;
		PoolPosType dmi_pool_used_;        // How many items used in the pool

		MatrixRow *matrix_;                // The first row is for starting

		DictExtPara *dep_;                 // Parameter used to extend DMI nodes.

		NPredictItem *npre_items_;         // Used to do prediction
		size_t npre_items_len_;

		// The starting positions and lemma ids for the full sentence candidate.
		size_t lma_id_num_;
		uint16 lma_start_[kMaxRowNum];     // Counted in spelling ids.
		LemmaIdType lma_id_[kMaxRowNum];
		size_t fixed_lmas_;

		// If fixed_lmas_ is bigger than i,  Element i is used to indicate whether
		// the i'th lemma id in lma_id_ is the first candidate for that step.
		// If all candidates are the first one for that step, the whole string can be
		// decoded by the engine automatically, so no need to add it to user
		// dictionary. (We are considering to add it to user dictionary in the
		// future).
		uint8 fixed_lmas_no1_[kMaxRowNum];

		// Composing phrase
		ComposingPhrase c_phrase_;

		// If dmi_c_phrase_ is true, the decoder will try to match the
		// composing phrase (And definitely it will match successfully). If it
		// is false, the decoder will try to match lemmas items in dictionaries.
		bool dmi_c_phrase_;

		// The starting positions and spelling ids for the first full sentence
		// candidate.
		size_t spl_id_num_;                // Number of splling ids
		uint16 spl_start_[kMaxRowNum];     // Starting positions
		uint16 spl_id_[kMaxRowNum];        // Spelling ids
		// Used to remember the last fixed position, counted in Hanzi.
		size_t fixed_hzs_;

		// Lemma Items with possibility score, two purposes:
		// 1. In Viterbi decoding, this buffer is used to get all possible candidates
		// for current step;
		// 2. When the search is done, this buffer is used to get candiates from the
		// first un-fixed step and show them to the user.
		LmaPsbItem lpi_items_[kMaxLmaPsbItems];
		size_t lpi_total_;

		// Assign the pointers with NULL. The caller makes sure that all pointers are
		// not valid before calling it. This function only will be called in the
		// construction function and free_resource().
		void reset_pointers_to_null();

		bool alloc_resource();

		void free_resource();

		// Reset the search space totally.
		bool reset_search0();

		// Reset the search space from ch_pos step. For example, if the original
		// input Pinyin is "an", reset_search(1) will reset the search space to the
		// result of "a". If the given position is out of range, return false.
		// if clear_fixed_this_step is true, and the ch_pos step is a fixed step,
		// clear its fixed status. if clear_dmi_his_step is true, clear the DMI nodes.
		// If clear_mtrx_this_sTep is true, clear the mtrx nodes of this step.
		// The DMI nodes will be kept.
		//
		// Note: this function should not destroy content of pys_.
		bool reset_search(size_t ch_pos, bool clear_fixed_this_step,
		                  bool clear_dmi_this_step, bool clear_mtrx_this_step);

		// Delete a part of the content in pys_.
		void del_in_pys(size_t start, size_t len);

		// Delete a spelling id and its corresponding Chinese character, and merge
		// the fixed lemmas into the composing phrase.
		// del_spl_pos indicates which spelling id needs to be delete.
		// This function will update the lemma and spelling segmentation information.
		// The caller guarantees that fixed_lmas_ > 0 and del_spl_pos is within
		// the fixed lemmas.
		void merge_fixed_lmas(size_t del_spl_pos);

		// Get spelling start posistions and ids. The result will be stored in
		// spl_id_num_, spl_start_[], spl_id_[].
		// fixed_hzs_ will be also assigned.
		void get_spl_start_id();

		// Get all lemma ids with match the given spelling id stream(shorter than the
		// maximum length of a word).
		// If pfullsent is not NULL, means the full sentence candidate may be the
		// same with the coming lemma string, if so, remove that lemma.
		// The result is sorted in descendant order by the frequency score.
		size_t get_lpis(const uint16 *splid_str, size_t splid_str_len,
		                LmaPsbItem *lma_buf, size_t max_lma_buf,
		                const char16 *pfullsent, bool sort_by_psb);

		uint16 get_lemma_str(LemmaIdType id_lemma, char16 *str_buf, uint16 str_max);

		uint16 get_lemma_splids(LemmaIdType id_lemma, uint16 *splids,
		                        uint16 splids_max, bool arg_valid);


		// Extend a DMI node with a spelling id. ext_len is the length of the rows
		// to extend, actually, it is the size of the spelling string of splid.
		// return value can be 1 or 0.
		// 1 means a new DMI is filled in (dmi_pool_used_ is the next blank DMI in
		// the pool).
		// 0 means either the dmi node can not be extended with splid, or the splid
		// is a Shengmu id, which is only used to get lpi_items, or the result node
		// in DictTrie has no son, it is not nccessary to keep the new DMI.
		//
		// This function modifies the content of lpi_items_ and lpi_total_.
		// lpi_items_ is used to get the LmaPsbItem list, lpi_total_ returns the size.
		// The function's returned value has no relation with the value of lpi_num.
		//
		// If dmi == NULL, this function will extend the root node of DictTrie
		//
		// This function will not change dmi_nd_pool_used_. Please change it after
		// calling this function if necessary.
		//
		// The caller should guarantees that NULL != dep.
		size_t extend_dmi(DictExtPara *dep, DictMatchInfo *dmi_s);

		// Extend dmi for the composing phrase.
		size_t extend_dmi_c(DictExtPara *dep, DictMatchInfo *dmi_s);

		// Extend a MatrixNode with the give LmaPsbItem list.
		// res_row is the destination row number.
		// This function does not change mtrx_nd_pool_used_. Please change it after
		// calling this function if necessary.
		// return 0 always.
		size_t extend_mtrx_nd(MatrixNode *mtrx_nd, LmaPsbItem lpi_items[],
		                      size_t lpi_num, PoolPosType dmi_fr, size_t res_row);


		// Try to find a dmi node at step_to position, and the found dmi node should
		// match the given spelling id strings.
		PoolPosType match_dmi(size_t step_to, uint16 spl_ids[], uint16 spl_id_num);

		bool add_char(char ch);
		bool prepare_add_char(char ch);

		// Called after prepare_add_char, so the input char has been saved.
		bool add_char_qwerty();

		// Prepare candidates from the last fixed hanzi position.
		void prepare_candidates();

		// Is the character in step pos a splitter character?
		// The caller guarantees that the position is valid.
		bool is_split_at(uint16 pos);

		void fill_dmi(DictMatchInfo *dmi, MileStoneHandle *handles,
		              PoolPosType dmi_fr,
		              uint16 spl_id, uint16 node_num, unsigned char dict_level,
		              bool splid_end_split, unsigned char splstr_len,
		              unsigned char all_full_id);

		size_t inner_predict(const char16 fixed_scis_ids[], uint16 scis_num,
		                     char16 predict_buf[][kMaxPredictSize + 1],
		                     size_t buf_len);

		// Add the first candidate to the user dictionary.
		bool try_add_cand0_to_userdict();

		// Add a user lemma to the user dictionary. This lemma is a subset of
		// candidate 0. lma_from is from which lemma in lma_ids_, lma_num is the
		// number of lemmas to be combined together as a new lemma. The caller
		// gurantees that the combined new lemma's length is less or equal to
		// kMaxLemmaSize.
		bool add_lma_to_userdict(uint16 lma_from, uint16 lma_num, float score);

		// Update dictionary frequencies.
		void update_dict_freq();

		void debug_print_dmi(PoolPosType dmi_pos, uint16 nest_level);

	public:
		MatrixSearch();
		~MatrixSearch();

    //	bool init(const char *fn_sys_dict, const char *fn_usr_dict);
        bool init(QString &fn_sys_dict, QString& fn_usr_dict);

    //	bool init_fd(int sys_fd, long start_offset, long length,
    //	             const char *fn_usr_dict);

		void set_max_lens(size_t max_sps_len, size_t max_hzs_len);

		void close();

		void flush_cache();

		void set_xi_an_switch(bool xi_an_enabled);

		bool get_xi_an_switch();

		// Reset the search space. Equivalent to reset_search(0).
		// If inited, always return true;
		bool reset_search();

		// Search a Pinyin string.
		// Return value is the position successfully parsed.
		size_t search(const char *py, size_t py_len);

		// Used to delete something in the Pinyin string kept by the engine, and do
		// a re-search.
		// Return value is the new length of Pinyin string kept by the engine which
		// is parsed successfully.
		// If is_pos_in_splid is false, pos is used to indicate that pos-th Pinyin
		// character needs to be deleted. If is_pos_in_splid is true, all Pinyin
		// characters for pos-th spelling id needs to be deleted.
		// If the deleted character(s) is just after a fixed lemma or sub lemma in
		// composing phrase, clear_fixed_this_step indicates whether we needs to
		// unlock the last fixed lemma or sub lemma.
		// If is_pos_in_splid is false, and pos-th character is in the range for the
		// fixed lemmas or composing string, this function will do nothing and just
		// return the result of the previous search.
		size_t delsearch(size_t pos, bool is_pos_in_splid,
		                 bool clear_fixed_this_step);

		// Get the number of candiates, called after search().
		size_t get_candidate_num();

		// Get the Pinyin string stored by the engine.
		// *decoded_len returns the length of the successfully decoded string.
		const char *get_pystr(size_t *decoded_len);

		// Get the spelling boundaries for the first sentence candidate.
		// Number of spellings will be returned. The number of valid elements in
		// spl_start is one more than the return value because the last one is used
		// to indicate the beginning of the next un-input speling.
		// For a Pinyin "women", the returned value is 2, spl_start is [0, 2, 5] .
		size_t get_spl_start(const uint16 *&spl_start);

		// Get one candiate string. If full sentence candidate is available, it will
		// be the first one.
		char16 *get_candidate(size_t cand_id, char16 *cand_str, size_t max_len);

		// Get the first candiate, which is a "full sentence".
		// retstr_len is not NULL, it will be used to return the string length.
		// If only_unfixed is true, only unfixed part will be fetched.
		char16 *get_candidate0(char16 *cand_str, size_t max_len,
		                       uint16 *retstr_len, bool only_unfixed);

		// Choose a candidate. The decoder will do a search after the fixed position.
		size_t choose(size_t cand_id);

		// Cancel the last choosing operation, and return the new number of choices.
		size_t cancel_last_choice();

		// Get the length of fixed Hanzis.
		size_t get_fixedlen();

		size_t get_predicts(const char16 fixed_buf[],
		                    char16 predict_buf[][kMaxPredictSize + 1],
		                    size_t buf_len);
	};
}

#endif  // PINYINIME_ANDPY_INCLUDE_MATRIXSEARCH_H__
